// 实现 Trie (前缀树)： https://leetcode-cn.com/problems/implement-trie-prefix-tree/

package main

// 使用map 实现：
// map 写法， 搜索的两个方法 可以提成一个公共的方法的，代码大量重复
type Trie struct {
	// 使用map 就不需要保存当前的节点了
	Children map[byte]*Trie

	isWord bool
}


func Constructor() Trie {
	return Trie{
		Children: make(map[byte]*Trie, 0),
	}
}


func (this *Trie) Insert(word string)  {
	cur := this
	w := []byte(word)
	for _, c := range w {
		// 不存在创建
		if _, ok := cur.Children[c]; !ok {
			// 创建
			node := Constructor()
			cur.Children[c] = &node
		}
		// cur 移动
		cur = cur.Children[c]
	}
	// 将末尾节点置为 true
	cur.isWord = true
}


func (this *Trie) Search(word string) bool {
	// 和 寻找开头的方法是一样的
	cur := this
	w := []byte(word)
	for _, c := range w {
		// 不存在直接返回错误
		if _, ok := cur.Children[c]; !ok {
			return false
		}
		// cur 移动
		cur = cur.Children[c]
	}
	return cur.isWord
}


func (this *Trie) StartsWith(prefix string) bool {
	// 和 寻找单词的方法是一样的
	cur := this
	w := []byte(prefix)
	for _, c := range w {
		// 不存在直接返回错误
		if _, ok := cur.Children[c]; !ok {
			return false
		}
		// cur 移动
		cur = cur.Children[c]
	}
	return true
}


/**
 * Your Trie object will be instantiated and called as such:
 * obj := Constructor();
 * obj.Insert(word);
 * param_2 := obj.Search(word);
 * param_3 := obj.StartsWith(prefix);
 */



// 数组索引实现的 hash
// 使用map 实现
type Trie struct {
	// 使用索引，类似于 hash的功能
	Children [26]*Trie

	isWord bool
}


func Constructor() Trie {
	return Trie{}
}


func (this *Trie) Insert(word string)  {
	cur := this
	w := []byte(word)
	for _, c := range w {
		// 不存在创建
		index := c - 'a'
		if cur.Children[index] == nil {
			// 创建
			cur.Children[index] = &Trie{}
		}
		// cur 移动
		cur = cur.Children[index]
	}
	// 将末尾节点置为 true
	cur.isWord = true
}


func (this *Trie) Search(word string) bool {
	// 和 寻找开头的方法是一样的
	cur := this
	w := []byte(word)
	for _, c := range w {
		index := c - 'a'
		// 不存在直接返回错误
		if cur.Children[index] == nil {
			return false
		}
		// cur 移动
		cur = cur.Children[index]
	}
	return cur.isWord
}


func (this *Trie) StartsWith(prefix string) bool {
	// 和 寻找单词的方法是一样的
	cur := this
	w := []byte(prefix)
	for _, c := range w {
		index := c - 'a'
		// 不存在直接返回错误
		if cur.Children[index] == nil {
			return false
		}
		// cur 移动
		cur = cur.Children[index]
	}
	return true
}


/**
 * Your Trie object will be instantiated and called as such:
 * obj := Constructor();
 * obj.Insert(word);
 * param_2 := obj.Search(word);
 * param_3 := obj.StartsWith(prefix);
 */
